Several computational problems in phylogenetic reconstruction can beformulated as restrictions of the following general problem: given a formula inconjunctive normal form where the literals are rooted triples, is there arooted binary tree that satisfies the formula? If the formulas do not containdisjunctions, the problem becomes the famous rooted triple consistency problem,which can be solved in polynomial time by an algorithm of Aho, Sagiv,Szymanski, and Ullman. If the clauses in the formulas are restricted todisjunctions of negated triples, Ng, Steel, and Wormald showed that the problemremains NP-complete. We systematically study the computational complexity ofthe problem for all such restrictions of the clauses in the input formula. Forcertain restricted disjunctions of triples we present an algorithm that hassub-quadratic running time and is asymptotically as fast as the fastest knownalgorithm for the rooted triple consistency problem. We also show that anyrestriction of the general rooted phylogeny problem that does not fall into ourtractable class is NP-complete, using known results about the complexity ofBoolean constraint satisfaction problems. Finally, we present a pebble gameargument that shows that the rooted triple consistency problem (and also allgeneralizations studied in this paper) cannot be solved by Datalog.
展开▼
